Threats to Terrestrial Radio
AM and FM terrestrial radio broadcasters are beginning to experience intense, new competition that, at a minimum, will reduce their market values and may threaten their very survival. Satellite radio threatens to dominate the mobile market, especially if tiered subscription services are introduced to allow users the option of free, commercial-based listening as described in related patent application Ser. No. 11/305,379 “TIERED SUBSCRIPTION BROADCAST SYSTEM.” Satellite radio is also a competitive threat to terrestrial radio's fixed playback devices (herein used synonymously with “receivers”) such as those used at work and home, although that threat is blunted somewhat by satellite radio's need for a clear view of the sky. Terrestrial radio's fixed user base is also threatened by Internet radio. And both mobile and fixed users are spending more time listening to recorded music of their choosing on MP3 players, iPods™ and similar devices. Other threats are on the horizon. For example, Qualcomm has recently announced it will offer a television and audio broadcast service through cell phone providers. Considering all the threats to AM and FM, it is conceivable that, a decade hence, terrestrial radio will be left with only a small fraction of its current user base.
The main competitive threats to terrestrial radio have the advantages of offering                a much wider range of music genres;        commercial free music; and        national coverage without any user input (e.g., retuning a playback device).        
For example, Apple's 60 GB iPod™ can hold over 1,000 hours of music, allowing a user to store almost any personal music collection of many different genres. The user can select a genre from the iPod's™ menu, hear only songs of that type, and switch genres whenever he desires. There are no commercials on an iPod™ and, clearly, it works in any part of the world. Similarly, Sirius and XM Satellite Radio are each offering nation-wide coverage with approximately 60 commercial free channels of different music types.
Whereas an “oldies” FM station will broadcast popular songs from several decades, Sirius currently has five distinct channels, one each devoted exclusively to music from the 1950s, 1960s, 1970s and 1980s, plus a Swing channel from the 1940s. XM has six “decade channels”, one each for the 1940s, 1950s, 1960s, 1970s, 1980s and 1990s. Sirius has four jazz channels with different genres of jazz (contemporary, smooth, classic and swing), three Latin channels (Latin Pop, Mexicana and Caribbean Dance), and three classical channels (opera, symphonic and classical pops). In contrast, even some major markets now have no classical terrestrial radio stations.
In the mobile market, satellite radio has the additional advantage of seamless, coast-to-coast coverage. With terrestrial radio, as a user drives from one city to the next, she must retune her playback device to try and find a new station of the same genre to which she was listening. In contrast, satellite radio's signal is the same across the entire nation and requires no retuning from city to city.
Another advantage of iPods™ and satellite radio over analog terrestrial radio is the ability to display information on a song (e.g., title, artist, date of release) while the song is playing. Many users find this information of great value. (Digital terrestrial radio can offer this service, but is not yet in widespread use.)
Because of these competitive advantages, iPods and satellite radio have been adopted at unprecedented rates. Both products were introduced late in 2001. Approximately three years later, at the end of 2004, Apple had sold over 10 million iPods and satellite radio had over 4 million subscribers. Both technologies are still in rapid growth mode, with more than half of their total sales through 2004 being in the last year of that period. Hence there is a real possibility that, within a decade, terrestrial radio will lose most of its user base. One object of the present invention is to allow terrestrial radio broadcasters to compete effectively against these new technologies by, among other things:                offering numerous channels of different genres of CD quality sound within the same spectrum that currently supports only one channel of a single genre at lower audio quality;        offering national or wider coverage with no retuning required by the user;        displaying song title and other information while the song is being played;        allowing access to the numerous channels of entertainment on either a commercial-free, subscription-based basis or a free, commercial-supported basis;        allowing instant access to traffic, weather, stock prices, and similar information, specifically tailored to the user's interests;        offering music and other entertainment for sale to the user in a more user-friendly manner than with current systems; and        providing sponsors with precise numbers of users reached and their demographics.Drawbacks of Terrestrial Radio Threats Overcome by the Present Invention        
Each of the competitive threats to terrestrial radio has its own drawbacks, and it is an object of the present invention to offer a service that retains the advantages of the threats, while minimizing their drawbacks.
Because it is at a much higher frequency than terrestrial radio, satellite radio does not penetrate buildings, dense trees, or other similar barriers, causing dropouts in mobile receivers and lack of service in many fixed locations. By allowing satellite radio type services to be offered over the existing terrestrial radio frequencies, which penetrate barriers much better, the invention removes much of that drawback of satellite radio.
Internet radio requires an Internet connection and therefore has limited applicability to mobile users. By allowing Internet radio type services to be offered over the existing terrestrial radio frequencies, the invention removes that drawback of Internet radio. Further, current legal proceedings under the Digital Millennium Copyright Act (DMCA) are imposing a royalty structure that some claim may make Internet radio uneconomic. In contrast, the DMCA exempts digital broadcasts from FCC-licensed terrestrial broadcast stations from that royalty structure.
iPods™ and similar music playback devices have three drawbacks that are removed by the present invention. First, the user must spend considerable time and money to amass a satisfactory music collection. While a 60 GB iPod can hold 1,000 hours of music, it takes at least 100 hours of the user's time to load that music from CDs, and ten times that if the music is to be properly organized (e.g., rating each album or track, creating playlists, etc.). Similarly, choosing, downloading, and organizing 1,000 hours of music from Apple's iTunes Music Store™ would take an enormous amount of time. In both cases, the cost to acquire 1,000 hours of music is very high (approximately $15,000 for 1,000 CDs, each an hour long and costing an average of $15, either in physical or iTunes™ form). It is a further object of the present invention to offer a more user-friendly experience, requiring little or no user interaction in order to have access to a large library of music, well organized for listening pleasure, allowing the user to skip songs not to her liking, to access a particular song on demand, and to have other desirable aspects of an iPod™ like device. It is a further object of the present invention to make a large, diverse library of music available to users at a reasonable cost that also is economically attractive to music publishers and broadcasters.
A second disadvantage of iPod™ like devices and previous attempts to create user specific listening experiences is their lack of a “surprise factor” in which users are exposed to music they have never heard before or had forgotten existed. This surprise factor is greatly desired by many users, at least some of the time, and is one reason proponents of satellite radio do not see iPods™ and similar devices as direct competitors. It is a further object of this invention to maintain the surprise factor, while still allowing the user to skip unwanted songs and have other desirable features of an iPod™ like device.
A third disadvantage of iPod™ like devices is the lack of professional presentation of music tracks to be played. While users sometimes prefer to hear music in the order they have specified and without any extra information or introduction (hereafter called “music only mode”), at other times they prefer music as it is now broadcast on the AM, FM and satellite radio bands, with introductions by DJs and in an order that has been professionally selected (hereafter called “DJ mode”). It is a further object of the present invention to allow users to choose which of these two modes they prefer, to switch back and forth from one mode to the other, and to control the amount of DJ talk when in DJ mode. This also provides an advantage over satellite and Internet radio, where the user has no control over the nature of the broadcast.
Internet radio and, to a lesser extent, satellite radio and iPods™ suffer from lower than CD quality audio. It is a further object of the invention to allow CD or higher quality audio broadcasts within a spectrum allocation that previously could not support such broadcasts.
The Opportunity and the Challenge
If current trends in disk drive costs continue, by 2015 a drive costing $200 will hold approximately 150 TB (each terabyte equaling 1E12 bytes) and be capable of storing over 20,000 DVD-quality, full-length movies or 50 million iPod™-quality, 3-minute songs, or any mixture thereof.
As of January 2005, Netlflix's huge library of mail-order rental DVDs boasted “over 30,000” movie titles in its library and Apple's iTunes Music Store™ claimed “more than one million” songs for sale. Therefore it is likely that, sometime in the near future, a $200 disk drive will be capable of storing a library consisting of all commercially viable movies and music ever produced in the world.
While the discussion which follows assumes such a 150 TB drive, the present invention provides significant benefits with even a 100 GB drive, whose cost today is well under $100. Such a 100 GB drive can store 1,700 hours of iPod-quality music. If divided into 30 channels of different music genres, each genre can have almost 60 hours of music and, as described below, this library is continually updated. Thus, the following discussion which is based on a 150 TB drive is for illustrative purposes only and does not limit the scope of the invention to a future time frame when a 150 TB drive is cost-effective in consumer electronics devices.
This abundance of storage creates both a major opportunity and a major problem for content providers. The opportunity is to store a library of music, movies and other media in an inexpensive playback device which gives users instantaneous access to virtually any music, movie or other media ever produced. While solving some problems, this approach creates others which are solved by the present invention:                The value of the content would be too great for a consumer to afford. At $25 per movie and $1 per song, the content on a 150 TB disk would be worth between $500,000 and $50,000,000, dwarfing the $200 cost of the disk drive itself.        The time to download enough media to even partly fill the disk drive would be prohibitive. As explained below, bandwidth is already much dearer than storage and is likely to stay that way.        If, to avoid long download times, the content is preloaded at the factory when the playback device is manufactured (or at the store where the playback device is sold), new content would not be available to the user. New hit songs and hit movies are in the greatest demand and the greatest moneymakers for content providers.        Consumers would be overwhelmed by the number of choices in such a huge library.        Piracy would be exacerbated. If a pirate gained access to the content of the hard drive, he could wreak economic havoc on the content providers, whose entire libraries would now be compromised.        
It is an object of the present invention to overcome the deficiencies of current systems, while avoiding or minimizing the problems listed above. A number of techniques can be adapted for dealing with the fact that the value of the content library is more than users can afford, for example (but not by way of limitation):                Access to the entire library, or portions thereof, can be rented to the consumer for a period of time (e.g., monthly).        Access to portions of the library (e.g., a single song, the contents of a single CD, or a single movie) can be sold to the consumer, either on a permanent basis or for a specified number of plays (e.g., three plays of a song).        The user can be billed periodically based on usage of the library. (If such usage information is known, then royalties can be paid to copyright owners accordingly. Otherwise, a system similar to that used for paying royalties on blank tape would be used.)        
It is an object of the present invention to implement such techniques in a secure manner which allows faster, ideally almost instantaneous, access to desired content than is possible with the prior art. It does so through the use of secure protocols, detailed below, to limit access to authorized (paid) users, and to limit authorized users to those portions of the library to which they are entitled.
Moore's Law, Storage, and Communications
This section explains why communications bandwidth is likely to remain much more expensive than bandwidth, thereby increasing the need for the present invention.
In 1965, Gordon Moore of Intel postulated what is now known as Moore's Law, that the computing power of ICs doubles approximately every eighteen months to two years, at no increase in cost per IC. Moore was extremely prescient as this trend has continued for four decades, up to the present time, reducing computing costs by at least a factor of a million, and by some measures much more.
Because the technology for creating hard disk drives is closely coupled to that for creating ICs, the cost of mass storage has decreased by a comparable factor over the same period of time, and indications are that the process should continue for at least another decade, opening up new possibilities in media broadcasting and distribution as detailed herein.
An analog of Moore's Law also applies to communications, such as telephone calls or Internet access, at least at a technological level. That is, the cost of providing communications could fall approximately as fast as for computing if there were a totally free market. However, there has not been, and is unlikely to be a totally free market in communications, so communications costs are likely to remain high relative to storage costs.
For many years, regulation by the FCC and its foreign equivalents kept communications costs artificially high in an attempt to subsidize consumers and rural subscribers at the cost of business. While that barrier has been largely pulverized by the Internet and a political climate that is fiercely resistant to its regulation, the fundamental nature of communications seems to resist a truly free market in which prices are set by the available technology.
When, in the 1970's, Digital Equipment Corporation (DEC) developed minicomputers that were as fast as an IBM mainframe and sold for a fraction of the cost, DEC flourished and
IBM withered. Only by reinventing itself as a service company did IBM resuscitate itself. While IBM would have liked to prevent its customers from migrating to DEC's more efficient minicomputers, there was nothing IBM could do to stop them from purchasing and using those machines.
Similarly when, a decade later, SUN Microsystems developed servers based on microprocessors that were faster than DEC's minicomputers and sold for a fraction of the cost, SUN took over much of DEC's business. Again, while DEC would have dearly liked to stop this migration, it could not do so.
The same situation that applies to computers also applies to disk drives and other storage methods. When Moore's Law gives rise to a faster, larger, cheaper storage device, there is nothing existing suppliers can do to stop customers from buying it although, in contrast to the computer industry, disk drive manufacturers grasped that they must keep up with technology to stay alive, and are their own worst competitors.
However, the situation is totally different with communications. When a faster cable modem is developed, it does a person no good to buy one unless his cable company installs equipment which will communicate with that faster modem. Similarly, a faster DSL modem is at the mercy of the local telephone company's agenda. And, neither the cable company nor the phone company wants to cannibalize its high cost business-oriented services by offering inexpensive consumer service at those higher speeds.
Unlike computation and storage, communications is not a solitary activity. Two users who wish to communicate must do so over a network that is controlled by an entity with no interest in seeing prices drop precipitously, even though such savings are technologically possible due to an analog of Moore's Law. So, by its very nature, communications prevents a free market and communications costs are likely to decrease much more slowly than computation and storage costs.
Thus far, this section's discussion applies to “wired networks” (including fiber optics in that definition). When wireless communications are considered the situation is worse because the radio spectrum is a fixed, finite resource. If demand is great enough, a company can lay more fiber to increase communications capacity. But no one can create more spectrum. Hence decreases in wireless communications costs are likely to be even slower than for wired.
Storage vs. Communications Imbalance and Media Distribution
Current approaches to media distribution already suffer from an imbalance between storage and communications costs and, for the reasons discussed in the previous section, this imbalance is likely to worsen with time. Today, a consumer-level broadband modem operates at approximately 1 Mbps, so it takes roughly 15 hours to transfer just one DVD-quality, full-length movie over the Internet. In consequence, most movie sales and rentals today use physical transfer of DVDs, not electronic delivery. For example, users purchase a DVD at a retail store (e.g., Best Buy), purchase a DVD over the Internet for delivery by mail or other delivery service (e.g., Amazon), rent a DVD at a video store (e.g., Blockbuster), select a DVD over the Internet for delivery by mail or other delivery service (e.g., Netflix). Electronic delivery of movies, known as “video on demand,” is in its infancy and will likely use lower than DVD-quality video to cut transfer times to a reasonable level.
Music requires less bandwidth and is therefore more amenable to electronic delivery, as evidenced by the popularity of Apple's iTunes Music Store™. However, even here, the user is limited by communication speeds to download just a few songs at a time without enduring an overly long wait. Again using 1 Mbps as a typical consumer-level broadband connection, it takes 80 minutes to send a 60-minute-long music CD, and it would take five and a half days to completely load a 60 GB iPod™. And, since the stated data rate is a maximum, the actual download times would likely be twice as long.
It is a further object of the present invention to minimize the deleterious effects of the growing imbalance between storage and communications costs, leveraging spectrum allocations (equivalently bandwidth, or data communications rate). It does so by substituting plentiful storage for scarce spectrum in novel ways, thereby producing up to 100 times and greater improvement in the effective use of the spectrum.
Discussion of Prior Art
The use of memory at a broadcast receiver to increase user satisfaction is well known in the art. DirectTV, for example, offers a TiVo™ equipped satellite television receiver, which can store programs on a hard drive and play them back at a later time. Usually, both the content to be stored and the content to be played back at a later time are decided by the subscriber. TiVo™ also has the capability to note the user's viewing habits and, if there is space on the hard drive, record similar programs automatically. However, the playback is user controlled, as opposed to automatic and does not simulate the experience of a live broadcast.
In U.S. Pat. No. 6,785,656 “Method and apparatus for digital audio playback using local stored content” Patsiokas et at describe a similar system for use with digital satellite radio. Since Tivo| and its competitors are called PVRs (Personal Video Recorders), Patsiokas' invention might be called a PAR (Personal Audio Recorder). Weber et at US Patent Application 2003/0236843 also improves the user experience for broadcast radio by recording broadcast music onto a mass storage device and either allowing the user to specify a playlist for the recorded music, or generating a playlist based on observed user preferences. Juszkiewicz US Patent Application 2004/0199654 describes a system for use with the Internet, including usage reporting to the copyright owners for billing purposes.
In U.S. Pat. No. 6,564,003 Marko et at describe another use of memory with digital satellite radio. Marko demodulates the bit stream from a broadcaster, such as XM Satellite Radio, and records it on a memory medium (e.g., a recordable CD) for later playback at a location that either cannot receive the satellite signal or does not need real time reception. As in Patsiokas, the selection of the recorded program to be played back is subscriber controlled.
In US Patent Application 2004/0083487 Collens et at describe a media distribution system which delivers content to a user in encrypted form and then delivers keys to unlock the content on a specific playback device.
In US Patent Application 2004/0133923 Watson et at describe a digital home movie library in which a broadcaster wirelessly transmits movies to a set top box for storage onto a hard drive for later viewing by a viewer. Newly manufactured and refurbished set top boxes are preloaded with next month's content, approximately 30 movies, but do not become available until an appropriate time.
In US Patent Application 2004/0225519 Martin stores a library of multimedia works on a storage device and plays a selection based on user preferences. Martin stores a library of multimedia works on a storage device, the multimedia works in the library being inaccessible except upon unlocking, and selectively unlocks portions of the library based on preference information indicative of preferences of a user of the multimedia works. Fees assessed to the user and royalties paid to rights holders can be based on the media played by the user. The stored works may be received on a removable medium, or may be downloaded wirelessly or through a wired connection.
In US Patent Application 2002/0116277 “Portable audio system housing a preloaded purchaser selected library od [of] MP3 compressed music titles stored on a hard disk drive,” Kraft describes a system similar to the current iPod™ for purchasing music over the Internet from a source similar to Apple's iTunes Music Store™.
In US Patent Application 2003/0070174 Solomon describes a wireless video-on-demand system which uses a low bandwidth channel (e.g., FM and TV subcarriers, or paging bands) to send encrypted movies slower than real time. The movies are buffered in storage and, when completely received, made available on demand for VCR like viewing.
In US Patent Application 2004/0266336 Patsiokas et at describe a system for recording and time-shifting a broadcast so that the user does not experience signal dropouts when a live signal is not available. Patsiokas also facilitates the purchase of live or time-shifted broadcast content.
In U.S. Pat. No. 6,289,455 “Method and apparatus for preventing piracy of digital content” Kocher et at describe a secure CryptoFirewall which protects critical portions of memory so that cryptographic keys used by a cryptoprocessor are inaccessible to all other parts of the system. These keys are made inaccessible to avoid the danger of a pirate attempting to learn them, creating a CryptoFirewall in Kocher's terminology.
This architecture prevents the frequent error in the implementation of cryptographic systems of storing keys in normal read-write memory where the keys are potentially accessible to piracy. The thinking behind this frequent error is that keys need to be written when entered and read when used for encryption or decryption. While this is true, allowing keys to be read by parts of the system which have no need for them other than for piracy, is extremely dangerous.
In US Patent Application 2003/0014767 Stumphauzer has a user of a radio broadcast service generate a personalized playlist on a web site. The playlist is subsequently transferred to a receiver either by the broadcast service or the user. The receiver then monitors the available programming contents of all of the programming channels and determines if any of the programs being broadcast match any of the selections on the playlist. If a match exists, then the receiver automatically tunes in the channel playing the matching program.
In US Patent Application 2003/0129941 Kawamata et at buffer past signals to allow switch over to stored content when the signal is lost. The substituted content can be based on user preferences. Kawamata uses a directed, bidirectional channel such as a cell phone channel to communicate lost packets to a user of a unidirectional non-directed (i.e., broadcast) channel such as a satellite channel. Since, in normal operation, only a small fraction of packets is lost on the satellite channel, the higher cost associated with the cell phone channel is not as much of an issue as if the cell phone channel were used for the entire communication.
In U.S. Pat. No. 6,697,608 “Digital audio/visual receiver with recordable memory” King-Smith describes a broadcast receiver with memory to give the user a wider selection of content.
In U.S. Pat. No. 6,434,622 “Multicasting method and apparatus” Monteiro et at use multicasting over the Internet to target advertising based on user demographics.
In US Patent Application 2003/0236843 Weber et at use multicasting networks to provide enhanced personalization of playlists and demographically targeted advertisements.
In U.S. Pat. No. 6,845,230 Syed uses a GPS module and an uplink module (a reverse channel) to provide broadcast data specific to the receiver's location. The uplink is also used to transmit profile information defining the user's desired broadcast format, to dynamically update private keys used for authentication and decoding, and for buy activities.
In US Patent Application 2004/0133914 Smith et at simulate a broadcast of a number of channels using digital media content stored in memory. Targeted advertisements are inserted into the simulated broadcast which advertisements can depend on demographics, time of day, geographical location, and frequency of play of the advertisement.
In U.S. Pat. No. 6,163,683 Dunn et at use a mixture of analog and digital transmissions with multiple transmitters to cover a larger area than is possible with just one transmitter. The radio receiver automatically retunes to a new transmitter as it crosses from the area served by one transmitter into the area served by another transmitter. A secondary channel is used to control storage of program information at receivers for delayed playing and to allow for playing previously transmitted and stored material that is locale-specific (e.g., information on and ads for local hotels, gas stations, etc.).
In U.S. Pat. No. 6,725,022 Clayton et at also utilizes automatic retuning of receivers as a mobile receiver loses the signal from one transmitter and gains the signal from another transmitter of the same format. Clayton also makes use of wireless communication between an Internet gateway and receivers to personalize broadcasts; to allow the user to communicate preferences from a PC to his receiver; to communicate information to the user that is stored in the receiver (e.g., information on a broadcast that the user indicated interest in); to communicate information on purchases authorized by the user (e.g., by pressing a BUY button); and to communicate program material to the receiver for storage and later playback.
In U.S. Pat. No. 6,600,908 Chan uses inaudible digital information modulated onto an FM signal to convey traffic, stock, weather, sports, and similar information to a user of an FM radio. This information is made available “on demand” by the user pushing a button and allows the FM station to broadcast its normal media (e.g., music) without interruption for conveying the on demand information. Users can access the on demand information when they want, rather than at preset times of the station's choosing.
In US Patent Application 2004/0116070 “Method, system, and computer program product for providing multi-tiered broadcasting services,” filed Nov. 20, 2003, Fishman et at describe a tiered subscription system for use with satellite radio. The present invention gives the broadcaster greater control than Fishman, thereby providing a better experience for the subscriber and more effective exposure for the advertiser. For example, in the present invention, specific songs can be deleted to make room for ads, ads can be targeted to specific subscribers, ads are less likely to be lost in transmission, ads that are lost in transmission are replaced by similar ads, audit information is provided to the broadcaster and advertiser, and the radio receiver is more secure.
In U.S. Pat. No. 6,834,156 Marko et at increases bandwidth efficiency in a digital broadcast system by storing content segments such as musical recordings and prerecorded commercials in a local memory in the receiver. At least some of the locally stored content segments are encrypted. The transmission bandwidth requirement is reduced when a content segment index or identifier and progress data is transmitted in lieu of the corresponding content segment. Marko also allows the user to purchase a broadcast program by pressing a button, thereby initiating an information exchange with a distribution center, resulting in the requested broadcast being decrypted and stored on a portable storage device (e.g., an optical disc).
In U.S. Pat. No. 5,815,671 Morrison describes a system for customizing entertainment for individual subscribers which includes the possibility of offering commercial-free service to some subscribers and commercial-supported service to other subscribers. Further, commercials can be targeted to specific program subscriber groups. Morrison transmits program materials, commercials, announcements and other message materials, with program break flags and message flags interspersed to indicate where message materials (e.g. commercials) are to be inserted in the program materials, while the message flags identify the particular message to be inserted.
In U.S. Pat. No. 6,463,585 Hendricks et at describe a multiple channel architecture to allow demographically targeted TV advertising. Information reported by the receiver to the cable head end is used to generate billing for commercial advertisers, and to analyze viewer watching habits.
US Patent Application 2005/0222764 of Uyeki et at and related US Patent Application 2005/0222760 of Cabral et at describe vehicles navigation systems which utilize traffic information to facilitate routing. Similarly, the recently released Garmin 2370 Street Pilot and similar devices utilize traffic information obtained via satellite or FM radio to automatically calculate and suggest faster alternative routes.
The present invention can be viewed as using a highly advanced codebook to reduce the communications burden. Codebooks have been used for hundreds of years, with the international distress signal SOS being a very simple example. Instead of sending the message, “Help, I need assistance!” the operator sends the much shorter codeword “SOS” instead. Codebooks have been in use since at least the nineteenth century to compress transmissions. As noted by David Kahn in The Codebreakers (Macmillan, New York, 1967) pp. 189-190:
“Samuel F. B. Morse sent, “What hath God wrought!” in 1844. The next year his lawyer and promotional agent, Francis O. J. Smith, published a commercial code . . . Smith's pioneering venture was followed by dozens, then scores, then hundreds of commercial codes. Though a few had as many as 100,000 entries . . . most [were] in the neighborhood of Smith's 50,000-entry size . . . . And they greatly increased the number of phrases [as opposed to individual words], thereby raising their toll-saving potential.”
More modern work also uses codebooks for data compression with the widely used Huffman Coding and LZ (Lempel-Ziv) algorithm being prime examples. Huffman coding (D. A. Huffman, “A Method for the Construction of Minimum Redundancy Codes,” Proceedings of the IRE, vol. 40, pp 1098-1101, 1962) uses codes with short bit patterns to represent frequent source symbols and longer bit patterns to represent infrequent source symbols, much as Morse code uses a single dot for the letter E versus two dashes and two dots for the letter Z, taking three times as long to send a Z as an E (including inter-letter spacing). In “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977, pp 337-343, Ziv and Lempel note (page 337 bottom of first column): “In this paper, we describe a universal coding scheme which can be applied to any discrete source and whose performance is comparable to certain optimal fixed code book schemes designed for completely specified sources.” The LZ algorithm keeps a running codebook of bit sequences that have already been seen by the encoder and decoder, uses codewords to represent those sequences so they can be compressed when they are seen again, and creates extensions of the codebook (a form of update) as new sequences are seen. It is universal in the sense that, as the number of encoded source bits tends to infinity, the performance of the LZ algorithm is as almost as good as that of any other compression algorithm.
Codebooks have also been used in vector quantization of speech, video, and other information. Y. Linde, A. Buzo and R. M. Gray, “An algorithm for vector quantizer design,” IEEE Transactions on Communications, Vol. COM-28, pp. 84-95, January 1980, is the seminal reference in this area. Statistical clustering via the Lloyd algorithm (often called k-means) is used to design a reproduction codebook. A nearest neighbor search finds the best match for an input vector and an index, chosen from the “channel codebook,” is transmitted or stored. The decompression is a table lookup using the index to find the selected reproduction codeword. Linde's codebooks are precomputed (trained), but updateable versions (“codebook replenishment”) came soon after, especially for video coding. There is also a literature on adaptive algorithms, where codebooks are modified on the fly, and universal algorithms, where the codebook is composed of many subcodebooks. Unlike Huffman and LZ coding which is lossless, the vector quantization literature introduces distortion into the process.